package skewreduce.lib;

import java.util.Arrays;

public final class IntSparseArray implements SparseArray<Integer> {
	final int limit;
	int[] data;
	int[] indexes;
	int   numElem;
	
	public IntSparseArray(int capacity) {
		this.limit = capacity;
		if ( capacity < 64 ) {
			data = new int[capacity];
		} else {
			indexes = new int[ (capacity-2) >>> 2];
			data    = new int[ (capacity-2) >>> 2];
		}
	}
	
	@Override
	public Integer get(int i) {
		if ( indexes == null ) {
			return data[i];
		} else {
			int k = Arrays.binarySearch(indexes, 0, numElem, i);
			if ( k < 0 ) return 0; // does not exists
			return data[k];
		}
	}
	
	@Override
	public Integer set(int i,Integer item) {
		if ( indexes == null ) {
			int old = data[i];
			data[i] = item;
			return old;
		} else {
			int k = Arrays.binarySearch(indexes, 0, numElem, i);
			if ( k < 0 ) {
				// have to insert manually
				if ( numElem < indexes.length ) {
					// do sparse mode
					// update indexes
					k = -1 * (k + 1);
					System.arraycopy(indexes, k, indexes, k+1, numElem - k);
					indexes[k] = i;
					// update list
					data[k] = item;
				} else {
					// we hit the limit. convert to dense mode
					int[] newData = new int[limit];
					int x = 0;
					for ( int d : data ) {
						newData[indexes[x++]] = d;
					}
					indexes = null;
					data = newData;
					k = i;
				}
				++numElem;
			}
			return data[k];
		}
	}
	
	public int size() { return numElem; }

	@Override
	public int dimension() {
		return limit;
	}
}
